# 直接插入排序python
# 插入排序的基本思想是：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
# 算法描述：
# 1.从第一个元素开始，该元素可以认为已经被排序；
# 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
# 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
# 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
# 5.将新元素插入到该位置后；
# 6.重复步骤2~5。
# 直接插入排序python代码


def InsertSort1(items):
    number=len(items)
    for i in range(0,number):
        if i !=0: #i相当于哨兵，记录每次插入到第几个数
            for j in range(0,i): #从前i-1个有序数列里查找，并完成插入
                if items[j]>items[i]:
                    items[j],items[i]=items[i],items[j]
    return items

def InsertSort2(items):
    number=len(items)
    for i in range(1,number):
        key=items[i] #添加哨兵，即要排序的元素
        j=i-1
        while j>=0 and key<items[j]:
            #如果要排序的元素比nums[j]要小
            items[j+1]=items[j]
            j-=1
        items[j+1]=key
    return items

def bin_InsertSort(items):
    number=len(items)
    for i in range(1,number):
        key=items[i]
        left,right=0,i-1
        #使用二分法查找插入位置
        while left <= right:
            mid=(left+right)//2
            if items[mid]>key:
                right=mid-1  #如果mid对应元素偏大，通过减小右值减小mid
            else:
                left=mid+1
        #找到插入位置，将items[i]--items[left]的元素向后移动一位
        for j in range(i,left,-1):
            items[j]=items[j-1]
        #将key插入到正确位置
        items[left]=key
    return items

#计算时间代码
import time
start=time.time()
print(InsertSort1([3,4,2,9,1]))
end=time.time()
print(end-start)

start=time.time()
print(InsertSort2([3,4,2,9,1]))
end=time.time()
print(end-start)

start=time.time()
print(bin_InsertSort([3,4,2,9,1]))
end=time.time()
print(end-start)

#items=[3,4,2,9,1]
#print(InsertSort(items))